1. Field of the Invention
The present invention relates generally to data sorting apparatus and sorting methods and, more particularly, to a data sorting apparatus for sorting a large number of applied data in predetermined order in a short time and to a sorting method therefor. The invention has a particular applicability to sorting processors applicable to computer systems.
2. Description of the Background Art
In a computer system, in general, a processing for rearranging a large number of applied data in a predetermined order, e.g., in descending order or ascending order of values of data, i.e., a sorting processing is often carried out. Since the sorting processing is a fundamental processing in the computer system, various application programs for the sorting processing have conventionally been developed and widely used. Thus, studies for achieving a faster sorting processing were commenced at approximately the same time as the birth of computer systems and have been continued. A conventional sorting processing which has been known mainly employs algorithms, and hence, the processing is carried out on the basis of software, i.e., software for carrying out sorting.
A proposal for carrying out sorting processing by using hardware is also known. That is, machines dedicated for carrying out sorting processing, called sorters, integrated circuit devices dedicated for sorting processing, called sorting processors, and the like have conventionally been developed. However, a sorting processor that has a sufficient performance and is able to process a large amount of data at a high speed has not yet been developed irrespective of its great demand.
FIG. 9 is a circuit block diagram of a conventional sorting apparatus employing hardware. This sorting apparatus is disclosed in Japanese Patent Publication No. 61-2211. With reference to FIG. 9, the sorting apparatus includes n cell circuits 11-1n each including a register for holding data of 32 bits. n data to be sorted are first held in n cell circuits 11-1n, respectively. Two adjacent circuits of n cell circuits 11-1n are connected with each other, so that two data can be exchanged between the circuits in response to the result of comparison between the two compared data. Respective cell circuits 11-1n are connected to receive a sorting start signal 3a, an initial state setting signal 3b and a clock signal 3c having a predetermined frequency. Odd-numbered cell circuits 11, 13, . . . of cell circuits 11-1n are connected to receive a designation signal 3d, while even-numbered cell circuits 12, 14, . . . are connected to receive a designation signal 3e. A control signal generating unit 2 applies or receives various control signals and data to or from an external apparatus, to generate control signals 3a, 3b, 3c, 3d and 3e for controlling cell circuits 11-1n.
In operation, all cell circuits 11-1n are reset in response to initial state setting signal 3b generated from control signal generating unit 2. Then, n data to be sorted are held in n registers (not shown) provided in cell circuits 11-1n, respectively. After control signal generating unit 2 generates sorting start signal 3a, n cell circuits 11-1n respond to clock signal 3c to carry out the following sorting operation. A description will now be given on an example in which the applied n data are rearranged in ascending order by sorting.
The sorting operation is carried out by repetition of first and second operation steps. In the first step, a comparison is made between data in each of the odd cell circuits and that in each of the even cell circuits located over the odd cell circuits. When data in each even cell circuit is smaller than that in each odd cell circuit, the two data are exchanged therebetween. The above-described comparison processing and exchange processing are carried out at a time between any adjacent odd and even cell circuits. In the second step, a comparison is made between data held in each even cell circuit and that held in each odd cell circuit located over the even cell circuit. When the data in the odd cell circuit is smaller than that in the even cell circuit, the held data are exchanged between those two cell circuits. Accordingly, repetition of the first and second operation steps by (n-1) times results in the end of the sorting of the applied n data. It is pointed out that the comparison and exchange operation that is required until the sorting processing is completed is determined depending on the number of data to be sorted. That is, when n data are applied, it is necessary to repeat the comparison and exchange operation by (n-1) times, i.e., approximately n times. This means that the time required for the sorting processing is increased in proportion to the number of data to be sorted.
Accordingly, when 10,000 data to be sorted are applied, for example, the comparison and exchange operation is repeated by 9999 times, i.e., approximately 10000 times. However, depending on the order of data to be initially applied, it is sometimes unnecessary to inevitably repeat the comparison and exchange operation by approximately 10,000 times. More specifically, depending on the order of data to be initially applied, there is a case where applied data are arranged in a desired order by repetition of the comparison and exchange operation by e.g., 5000 times. In the conventional sorting apparatus shown in FIG. 9, since the data comparison and exchange operation is necessarily repeated by approximately 10000 times even in such a case, the time required for processing is increased by carrying out unnecessary processings. That is to say, in the conventional sorting apparatus, in order to carry out the sorting processing, a fixed time that is determined depending on the number of data to be sorted is required, thereby preventing the sorting processing from being carried out in a short time. It is pointed out in general that the sorting processing is completed by repeating the data comparison and exchange operation by a number less than the number of applied data.